package com.dhu.graph.shortestPath;

import com.dhu.graph.basic.GraphImpls.EdgeWeightedDiGraph;
import com.dhu.graph.basic.edge.DirectedEdge;
import com.dhu.graph.digraph.TopoLogical;

import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-13
 * @ Description：
 * 解决加权有向无环图的最短路径，能在线性时间内完成，比Dijskatra算法快许多
 * AcyclicSP 算法和Dijskatra算法的区别在于不依赖优先队列，而是按照拓扑排序的顺序来relax顶点
 * @ Modified By：
 * @ Version:
 */
public class AcyclicSP {
    public DirectedEdge[] edgeTo;
    private double[] distTo;

    public AcyclicSP(EdgeWeightedDiGraph G, int s){
        this.edgeTo = new DirectedEdge[G.V()];
        this.distTo = new double[G.V()];
        for (int i = 1; i < G.V(); i++){
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[0] = 0.0;
        Stack<Integer> order = new TopoLogical(G).order();

        while (!order.isEmpty()){
            Integer v = order.pop();
            if (distTo[v] < Double.POSITIVE_INFINITY)
                relax(G, v);
        }
    }
    private void relax(EdgeWeightedDiGraph G, int s){
        for (DirectedEdge e : G.adj(s)) {
            int w = e.to();
            if (distTo[w] > distTo[s] + e.getWeight()){
                distTo[w] = distTo[s] + e.getWeight();
                edgeTo[w] = e;
            }
        }
    }
    public boolean hasPathTo(int v){
        return distTo[v] < Double.POSITIVE_INFINITY;
    }
    public double distTo(int v){
        return this.distTo[v];
    }
    public Iterable<DirectedEdge> pathTo(int v){
        Stack<DirectedEdge> edges = new Stack<>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[v]){
            edges.push(e);
        }
        return edges;
    }
}
